The present invention relates to distributed resource allocation, and, more particularly, to a method and apparatus for distributing sets of assignments to at least one agents.
Distributed resource allocation is a known computer science framework, generally applicable to multi agent systems in which it is required to distribute a certain amount of assignments among a given set of agents during a given time. This framework is presently exploited in many real-life areas, including satellite mission management, scheduling, logistics, timetabling, transportation and the like. In earth observation satellite management, for example, daily decisions have to be made for allocating different earth observation satellite at different times to perform different tasks, such as capturing images. These decisions can be taken for a long term period (e.g., year, month) and/or for a short term period (e.g., week, day, activity window). In any event, the decisions are typically based on both past knowledge and future estimations and are subjected to a plurality of constraints.
In transportation, it is oftentimes required to use a given set of vehicles to deliver merchandise to a large number of destinations while satisfying a variety of local and global constraints, such as time, capacity, predetermined routes and the like.
Generally, distributed resource allocation belongs to a set of mathematical problems known as constraint optimization problems, which is formally defined over a set of variables and a set of constraints where a variable may draw its value from a predefined domain. The mathematical problem involves the assignment of a value to each variable while satisfying at least a subset of the constraints. This is typically performed by defining an objective function and searching for a plurality of values to the variables such as to minimize or maximize the objective function. Several techniques are known for obtaining a solution to a constraint optimization problem. Representative examples include, without limitation complete or local search methods, and evolutionary computation.
However, there are still many distributed resource allocation problems which cannot be satisfactorily resolved by conventional computation techniques. Particularly, in problems belonging to the NP-hard complexity class, the execution time of the computation grows rapidly with the size of the problem (faster than a polynomial growth). All the more so, to obtain a solution for real life NP-hard problems, one is oftentimes required to perform auxiliary analyses which are not required in pure mathematical models.
For example, in the aforementioned problem of earth observation satellite management, the solution process includes a trajectory analysis, which is typically performed by an auxiliary procedure such as a satellite simulator. It is recognized that even for a few passes of a single satellite, the number of possible scan combinations is enormous. This number becomes prohibitively high when multiple satellites are concerned, because each satellite moves along a different trajectory and can point its sensor(s) to more than one direction. For agile satellites, the complexity of the problem is further enhanced due to the propulsion system of each satellite which moves the satellite about in orbit and controls its attitude.
Additionally, the operations performed by a single satellite form an interdependent series, whereby an operation made by the satellite at a particular moment may affect operations performed thereafter. This interdependence may be physical and/or logical. Logical interdependency arises when the user relates two or more imaging requests to one another, as in the case of a request to scan several areas on the same day, or a request for stereo acquisition, in which the same area has to be covered from different perspectives. Physical interdependency results from maneuvering operations of the satellite required for pointing, energy constraints, recorder overflow and communication and calibration periods. These dependencies further constrain the management problem, because the list of targets that can be imaged at any given moment depends on previously imaged targets and/or future imaging opportunities. When both the plurality of sensor directions and the interdependencies are taken into account, fulfilling all the request parameters (e.g., deadline for taking the image) and working around external constraints become highly challenging.
Several attempts have been made to obtain a near-optimal solution to the problem of earth observation satellite management. These attempts generally include the use of incomplete optimization algorithms utilizing heuristics and simplifying assumptions on the original problem.
U.S. Patent application No. 20040158832 treats each slice of the total timeframe as a would-be starting point for the remainder of the process. Thus, out of the entire set of possible states of the satellite, only two subsets are processed: a state in the examined timeframe and a sequence of states in timeframes that have already been examined.
Lemaître et al. [Michel Lemaître and Gérard Verfaillie, “Daily Management of an Earth Observation Satellite: Comparison of ILOG Solver With Dedicated Algorithms for Valued Constraint Satisfaction Problems”, Third ILOG International Users Meeting, Paris, France, 1997] formulate the earth observation satellite scheduling problem as a valued constrained satisfaction problem (VCSP). Specifically the problem is formulated using a set of variables (representing the images to be captured), a set of constrains and a mathematical valuation structure defined to assign a valuation for each constrain mirroring the importance one gives to its satisfaction. Approximate solutions to the problem were obtained using ILOG Solver™ commercial software and a special VCSP library.
Givry et al. [Simon de Givry, Gérard Verfaillie and Thomas Schiex, “Bounding the Optimum of Constraint Optimization Problems”, Gert Smolka, ed.: Principles and Practice of Constraint Programming—CP97, Third International Conference, Linz, Austria, 1997, 405-419] employ an order morphism simplification function so as to simplify the VCSP problem and to build lower bounds to the optimal valuation of the problem.
Other prior art of relevance include Lemaýtre M, Verfaillie G, Jouhaud F., Lachiver J-M and Bataille N, “Selecting and scheduling observations of agile satellites, Aerospace Science and Technology 2002, 6:367-381; and Wolfe W J and Sorensen S, “Three Scheduling Algorithms Applied to the Earth Observing Systems Domain”, INFORMS Journal on Management Science, 2000. 46(1).
The solutions provided by prior art techniques are far from being satisfactory. For example, prior art techniques, although defining a set of constrains in their mathematical formulation, practically compromise on the number of constraints for each satellite, thereby fail to provide an adequate solution to the problem.
There is thus a widely recognized need for, and it would be highly advantageous to have a method and apparatus for distributing sets of assignments to a plurality of agents, devoid the above limitations.